package sort;

import org.junit.Test;

import java.util.Arrays;

public class Demo {

    @Test
    public void test1() {
        //                                   j   i
        //               72  6  57  48  60  42  83  73  88  85
//        Integer[] arr = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
        Integer[] arr = {72, 78, 57, 88, 60, 42, 83, 73, 48, 71};
        int partition = partition(arr, 0, arr.length - 1);
        System.out.println(partition);
    }

    @Test
    public void test2() {
        Integer[] arr = {72, 78, 57, 88, 60, 42, 83, 73, 48, 71};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));

    }

    public static void quickSort(Comparable[] arr) {
        sort(arr, 0, arr.length-1);
    }

    public static void sort(Comparable[] arr, int lo, int hi) {
        if (hi <= lo) return;
        int partition = partition(arr, lo, hi);
        sort(arr, lo, partition - 1);
        sort(arr, partition + 1, hi);


    }

    public static int partition(Comparable[] arr, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        Comparable v = arr[lo];
        while (true) {
            while (less(arr[++i], v)) {
                if (i == hi) break;
            }
            while (less(v, arr[--j])) {
                if (j == lo)break;
            }
            if (i >= j) {
                break;
            }
            exch(arr, i, j);
        }
        exch(arr, j, lo);
        return j;
    }
//private static int partition(Comparable[] a, int lo, int hi) {
//    int i = lo;
//    int j = hi + 1;
//    Comparable v = a[lo];
//    while (true) {
//
//        // find item on lo to swap
//        while (less(a[++i], v)) {
//            if (i == hi) break;
//        }
//
//        // find item on hi to swap
//        while (less(v, a[--j])) {
//            if (j == lo) break;      // redundant since a[lo] acts as sentinel
//        }
//
//        // check if pointers cross
//        if (i >= j) break;
//
//        exch(a, i, j);
//    }
//
//    // put partitioning item v at a[j]
//    exch(a, lo, j);
//
//    // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
//    return j;
//}


//    private static int partition(Comparable[] a, int lo, int hi) {
//        int i = lo;
//        int j = hi + 1;
//        Comparable v = a[lo];
//        while (true) {
//            // find item on lo to swap
//            while (less(a[++i], v)) {
//                if (i == hi) break;
//            }
//            // find item on hi to swap
//            while (less(v, a[--j])) {
//                if (j == lo) break;      // redundant since a[lo] acts as sentinel
//            }
//            // check if pointers cross
//            if (i >= j) break;
//            exch(a, i, j);
//        }
//        // put partitioning item v at a[j]
//        exch(a, lo, j);
//        // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
//        return j;
//    }

    private static boolean less(Comparable i, Comparable j) {
        return i.compareTo(j) < 0;
    }

    private static void exch(Comparable[] arr, int i, int j) {
        Comparable comparable = arr[i];
        arr[i] = arr[j];
        arr[j] = comparable;
    }
}
